; 每个item 包括前，后指针

(define (make-deque)
    (let 
        (
            (front-ptr `())
            (rear-ptr `())
        )
        (define (set-front-ptr! item)
            (set! front-ptr item)
        )
        (define (set-rear-ptr! item)
            (set! rear-ptr item)
        )
        (define (empty-deque?) 
            (null? front-ptr)
        )
        
        (define (front-insert-deque! item)
            (let 
                ((new-pair (cons (cons item `()) `())))
                (cond 
                    ((empty-deque?)
                        (set-front-ptr! new-pair)
                        (set-rear-ptr! new-pair)
                    )
                    (else
                        (set-cdr! new-pairs front-ptr)
                        (set-cdr! (car front-ptr) new-pair)
                        (set-front-ptr! new-pair)
                    )
                )
            )
        )

        (define (rear-insert-deque! item)
            (let 
                ((new-pair (cons (cons item `()) `())))
                (cond 
                    ((empty-deque?)
                        (set-front-ptr! new-pair)
                        (set-rear-ptr! new-pair)
                    )
                    (else                       
                        
                        (set-cdr! (car new-pair) rear-ptr)                       
                        (set-cdr! rear-ptr new-pair)                        
                        (set-rear-ptr! new-pair)
                    )
                )
            )
        )

        (define (front-delete-deque!)
            (if (empty-deque?)
                (error "DELETE empty deque" deque)
                (begin   
                    (set-cdr! (car front-ptr) `())
                    (set-front-ptr! (cdr front-ptr))
                )
            )
        )

        (define (rear-delete-deque!)
            (if (empty-deque?)
                (error "DELETE empty deque" deque)
                (begin 
                    (set-cdr! rear-ptr `())
                    (set-rear-ptr! (cdr (car rear-ptr)))
                    (if (null? rear-ptr)
                        (set-front-ptr! `())
                    )
                )
            )
        )

        (define (print-deque) 
            (newline)           
            (display "deque:")
            (print-deque-iter front-ptr)            
        )

        (define (print-deque-iter ptr)
            (cond
                ((null? ptr)
                    `()
                )
                ((eq? rear-ptr ptr)                
                    (begin
                        (display (caar ptr))
                    )
                )
                (else 
                    (begin
                        (display (caar ptr))
                        (print-deque-iter (cdr ptr))
                    )
                )
            )
        )
    
        (define (dispatch m) 
            (cond 
                ((eq? m `set-front-ptr!) set-front-ptr!)
                ((eq? m `set-rear-ptr!) set-rear-ptr!)
                ((eq? m `empty-deque?) empty-deque?)
                ((eq? m `front-insert-deque!) front-insert-deque!)
                ((eq? m `rear-insert-deque!) rear-insert-deque!)
                ((eq? m `front-delete-deque!) front-delete-deque!)
                ((eq? m `rear-delete-deque!) rear-delete-deque!)
                ((eq? m `print-deque) print-deque)
                (else (error "...." m))
            )    
        )
        dispatch        
    )
)


(define q1 (make-deque))
((q1 `front-insert-deque!) `a)
((q1 `print-deque))
((q1 `rear-delete-deque!)) 
((q1 `print-deque))
((q1 `rear-insert-deque!) `b)
((q1 `print-deque))
((q1 `rear-insert-deque!) `c)
((q1 `print-deque))
((q1 `front-delete-deque!)) 
((q1 `print-deque))
((q1 `front-delete-deque!)) 
((q1 `print-deque))


(exit)


